package main.java.indi.zyj.sort;


public class MergeSort {

    public static void merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        internalMergeSort(arr, result, 0, len - 1);
    }

    // 归并排序
    private static void internalMergeSort(int[] arr, int[] result, int left, int right) {
        if (left < right){
            int mid = left + (left + right) / 2;
            internalMergeSort(arr, result, left, mid);
            internalMergeSort(arr, result, mid + 1, right);
            merge_sort_recursive(arr, result, left, mid, right);
        }
    }

    static void merge_sort_recursive(int[] arr, int[] result, int left, int mid, int right) {

        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right){
            result[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid){
            result[k++] = arr[i++];
        }
        while (j <= right){
            result[k++] = arr[j++];
        }

        //把数据复制回原数组
        for (i = 0; i < k; i++){
            arr[left + i] = result[i];
        }

    }








}
